##
中国大学mooc视频地址 程序设计与算法（二）算法基础
【搬运自taleyoung的印象笔记】
先来看个热身题
其中隐藏的分治的思维：
8 - 8 称，会发现无假币或有假币即在对应8枚中
4 - 4
2 - 2
1 - 1
一共需要4次完成 【思考一番 】
由此引出今天的主题
分治的典型应用（一）：归并排序
即 将一个数组用Mergesort函数分成两份，然后应用递归再次分成两份
然后应用Merge将这些组合起来
#include<iostream>
using namespace std;
int a[10] = {13,27,19,2,8,12,2,8,30,89};
int b[10];
void Merge(int a[],int s,int m,int e,int b[]){
int pb = 0; //用来标记b数组的下标
int p1 = s, p2 = m+1;
while(p1<=m && p2 <=e){ //这一步将两个已排序数组合并成一个数组
if(a[p1] < a[p2]){ //很具有技巧性！！
b[pb++] = a[p1++];
}
else b[pb++] = a[p2++];
}
while(p1 <= m) //用于担心一半用完一半未用完
b[pb++] = a[p1++];
while(p2 <= e)
b[pb++] = a[p2++];
for(int i = 0;i < e-s+1; i++){
a[s+i] = b[i];
}
}
void Mergesort(int a[],int s, int e, int b[]){
if(s < e){
int m = s + (e-s)/2;
Mergesort(a,s,m,b); //递归了
Mergesort(a,m+1,e,b);
Merge(a,s,m,e,b);
}
}
int main()
{
int size = sizeof(a)/sizeof(a[0]);
Mergesort(a,0,size-1,b);
for(int i = 0; i < size; i++)
cout << a[i] << ',';
cout << endl;
return 0;
}
分治的典型应用（二）：快速排序
本令k为a[0]，然后把数组中比k小的放在左面，比k大的放在右边，然后对左右两边再进行递归， 在放左放右的过程的算法十分精妙 需要仔细研究 就不细讲了 自己看代码把。
#include<iostream>
using namespace std;
int a[] = {93,27,30,2,8,30,89};
void swap(int &m,int &n){ //写交换函数，注意要取地址
int t = m;
m = n;
n = t;
}
void Quicksort(int a[], int s, int e){
if(s >= e)
return;
int i = s,j = e; //这步算法很精妙！i在最前 j在最后
int k = a[s]; //k为第一个数 即将作为分界数
while(i!=j){ //只要i!=j说明i和j还在走
while(i<j && a[j]>=k) // 一种情况下一直用while 使得跳出时是a[j]<k的时候 【k=a[i]】
j--;
swap(a[i],a[j]); //由上述while循环筛选出应该swap的对象 【k=a[j]】
while(i<j && a[i]<=k) // 此时k = a[j]
i++; //在while的情况下 i一直往前走 找出a[i]>k的时候跳出
swap(a[i],a[j]);
}
Quicksort(a,s,i-1); //对两边进行递归
Quicksort(a,i+1,e);
}
int main(){
int size = sizeof(a)/sizeof(a[0]);
Quicksort(a,0,size-1);
for(int i = 0; i < size; i++)
cout << a[i] <<',';
cout << endl;
return 0;
}
分治练习
例题一：输出前m大的数
给定一个数组包含n个元素，统计前m大的数并且把这m大的数从大到小输出
【具体输入输出见视频或查阅印象笔记】
思路：
1.应用归并排序的思维，令key = a[0] 然后比key大的放其后，比key小的放在前面，此步用arrangeRight函数实现
2.比较右侧a个比key大的数：
1)a=k -> 即为所求
2)a>k -> 即需要在a中继续1步，进行递归操作 arangeRight(k)
3)a
由上述分析可知，在2和3中不断递归 知道出现目标1 即1是递归的边界条件
#include
using namespace std;
void QuickSort(int a[], int s, int e){ //快排的标准模板 要熟练这种思想
if(s >= e) //这个是总的边界条件
return ;
int i = s,j = e;
int k = a[s];
while(i!=j){
while(i < j && a[j] >=k)
j–;
swap(a[i],a[j]);
while(i < j && a[i] <= k)
i++;
swap(a[i],a[j]);
}
QuickSort(a, s, i-1); //对前后两块再进行递归，用上面的边界条件终止
QuickSort(a, i+1,e);
}
void arrangeRight(int a[],int s,int e, int k){ //利用分治归并的思想写出来的
if(s >= e) //排除特殊情况
return ;
if( k== e-s+1) //总边界条件 用于跳出递归循环：含义是当递归到只剩一个比较时终止
return ;
int i = s,j = e;
int key = a[s]; //用key而非k 因为k是目标 下面还要比较进行再递归
while(i!=j){
while( i < j && a[j] >= key)
j–;
swap(a[i],a[j]);
while( i < j && a[i] <= key)
i++;
swap(a[i],a[j]);
}
if(k==e-i+1)
return ;
else if( k < e-i+1) //这几步递归的奥妙 见上述思路的分析可得
arrangeRight(a,i+1,e,k);
else if( k >= e-i+1)
arrangeRight(a,s,i-1,k-(e-i+1));
}
void printM(int a[],int n, int k){ //要会写这种函数块编程
arrangeRight(a,0,n-1,k); //参数别搞错了
QuickSort(a,n-k,n-1); //要排后k项，最后一位下标是n-1 即第一位是n-1-k+1=n-k
// for(int i = 6; i < 10; i++) //这样是越界的 参照下面的方法
// cout << a[i] << ‘,’;
while(k–) //这个技巧咋还不会呢！！！！
cout << a[–n] <<” “;
cout << endl ;
}
void swap(int &m, int &n){
int t = m;
m = n;
n = t;
}
int main()
{
int a[] = {1,4,7,2,5,8,3,6,9};
// int m = 4;
printM(a,9,4);
return 0;
}
例题二：求排列的逆序数
【具体输入输出见视频或查阅印象笔记】
此题思想类似于等值题目那道题一样。
此类方法的特点是充分利用数组有序的特点只遍历数组一次，比较两个数组中相等元素，不需o(n2)的复杂度，这种方法 我语言表达不出来，就像》。。算了 自己看带代码吧
#include <stdio.h>
int main()
{
int f[5] = {1,3,4,7,9};
int g[5] = {3,5,7,8,10};
int i=0, j = 0, count = 0;
while(i < 5&& j < 5){
if(f[i] == g[j]){
count++;
i++,j++;
}
else if(f[i] > g[j]){
j++;
}
else{
i++;
}
}
printf("%d",count);
return 0;
}